package quwei;

import java.util.Scanner;

public class Test4_3 {
    static String s1;
    static String s2;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("输入字符串s1：");
        s1=scanner.next();
        System.out.println("输入字符串s2：");
        s2=scanner.next();
        int len1=s1.length();                          //计算两个字符串的长度
        int len2=s2.length();     

        int[][] c=new int[len1+1][len2+1];             //存放公共子序列的最大长度
        int[][] b=new int[len1+1][len2+1];             //记录来源

        for(int i=0;i<=len1;i++)
            c[i][0]=0;                                 //初始化第一列为0
        for(int j=0;j<=len2;j++)
            c[0][j]=0;                                 //初始化第一行为0

        LCSL(c,b);                                     //求解最长公共子序列
        System.out.println("s1和s2的最长公共子序列长度是："+c[len1][len2]);
        System.out.print("s1和s2的最长公共子序列是：");
        print(len1,len2,b);                            //递归构造最长公共子序列最优解
    }

    /*求解最长公共子序列*/
    public static void LCSL(int[][] c,int[][] b) {
        int i,j;
        for(i=1;i<=c.length-1;i++) {                   //控制s1的序列，即遍历s1的每个字符
            for(j=1;j<=c[i].length-1;j++) {            //控制s2的序列，即用s1的字符与s2的所有字符进行比较

                if(s1.charAt(i-1)==s2.charAt(j-1)) {   //字符下标从0开始
                    //如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }
                else {
                    if(c[i][j-1]>=c[i-1][j]) {         //找出两者最大值，若相等默认取左侧
                        c[i][j]=c[i][j-1];             //取左侧值
                        b[i][j]=2;
                    }
                    else {
                        c[i][j]=c[i-1][j];             //取上面值
                        b[i][j]=3;
                    }
                }
            }
        }
    }

    /*递归构造最长公共子序列最优解*/
    public static void print(int i,int j,int[][] b) {
        if(i==0||j==0)
            return;                                    //递归结束条件
        if(b[i][j]==1) {                               //来源左上角
            print(i-1,j-1,b);
            System.out.print(s1.charAt(i-1));
        }
        else if(b[i][j]==2) 
            print(i,j-1,b);                            //来源左侧
        else
            print(i-1,j,b);                            //来源上面               
    }
}
